#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MAX_SIZE 100

// https://blog.csdn.net/qq_44075108/article/details/115435408

// 定义三元组结构
typedef struct
{
    int i; // 非零元素的行号(下标)
    int j; // 非零元素的列号(下标)
    int v; // 非零元素的值
} TriTupleNode;

// 定义稀疏矩阵
typedef struct
{
    TriTupleNode data[MAX_SIZE]; // 存储三元组的数组
    int m;                       // 矩阵行数
    int n;                       // 矩阵列数
    int t;                       // 矩阵非零元素个数
} SparseMatrix;

// 按矩阵形式打印输出矩阵
void printMatrix(SparseMatrix *M);
// 按三元组形式输出稀疏矩阵
void printMatrixByTriplet(SparseMatrix *M);

// 创建三元组的稀疏矩阵
void createTriTable(SparseMatrix *SM, int a[][5], int m, int n)
{
    // 非零元素统计
    int k = 0;

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // 非零元素
            if (a[i][j] != 0)
            {
                SM->data[k].i = i;
                SM->data[k].j = j;
                SM->data[k].v = a[i][j];
                k++;
            }
        }
    }

    SM->m = m;
    SM->n = n;
    SM->t = k;
}

// 矩阵一般转置法。 仅适用非零元素个数小于矩阵元素个数的情况
void transMatrix(SparseMatrix *A, SparseMatrix *B)
{
    B->m = A->n;
    B->n = A->m;
    B->t = A->t;
    if (B->t <= 0)
    {
        printf("B SparseMatrix no non-zero elements\n");
        return;
    }

    int k = 0;
    // 遍历A的列数
    for (int y = 0; y < A->n; y++)
    {
        // printf("------------->col =%d\n", y);
        // 每遍历一遍列时，遍历每个元素
        for (int x = 0; x < A->t; x++)
        {
            // printf("A.data[%d].j=%d ----y=%d\n", x, A->data[x].j, y);
            // 寻找等于当前列的元素。然后赋值给 B 的行
            if (A->data[x].j == y)
            {
                B->data[k].i = A->data[x].j;
                B->data[k].j = A->data[x].i;
                B->data[k].v = A->data[x].v;
                k++;
            }
        }
    }
}

// 快速转置算法
void fastTransMatrix(SparseMatrix *A, SparseMatrix *B)
{
    B->m = A->n;
    B->n = A->m;
    B->t = A->t;

    if (B->t <= 0)
    {
        printf("B SparseMatrix no non-zero elements\n");
        return;
    }

    // num[j] 存放 矩阵第 j 列上非零元素个数
    int *num = (int *)calloc(A->n + 1, 4);
    int *rowNext = (int *)calloc(A->m + 1, 4);
    int col;
    // 初始化
    for (col = 0; col < A->n; col++)
    {
        num[col] = 0;
    }
    // 计算每列非零元素个数
    for (int t = 0; t < A->t; t++)
    {
        num[A->data[t].j]++;
    }

    rowNext[0] = 0;
    // 给出 B 中每一行的起始点
    for (col = 1; col < A->n; col++)
    {
        rowNext[col] = rowNext[col - 1] + num[col - 1];
    }

    int k = 0;
    for (int p = 0; p < A->t; p++)
    {
        col = A->data[p].j;
        k = rowNext[col];
        B->data[k].i = A->data[p].j;
        B->data[k].j = A->data[p].i;
        B->data[k].v = A->data[p].v;
        ++rowNext[col];
    }
}

int main()
{
    int arr[3][5] = {{0, 1, 2, 3, 4}, {5, 0, 6, 7, 8}, {9, 10, 0, 1, 2}};
    SparseMatrix *SM = (SparseMatrix *)malloc(sizeof(SparseMatrix));
    createTriTable(SM, arr, 3, 5);
    printMatrix(SM);
    printMatrixByTriplet(SM);

    SparseMatrix *B = (SparseMatrix *)malloc(sizeof(SparseMatrix));
    // transMatrix(SM, B);
    fastTransMatrix(SM, B);
    printMatrix(B);
    printMatrixByTriplet(B);
    return 0;
}

// 按矩阵形式打印输出矩阵
void printMatrix(SparseMatrix *M)
{
    int **p = NULL;
    int i, j;
    // 申请全部行的首指针
    p = (int **)malloc(M->m * sizeof(int *));
    assert(p != NULL);

    for (i = 0; i < M->m; i++)
    {
        // 申请列的指针
        *(p + i) = (int *)malloc(M->n * sizeof(int));
        if (*(p + i) == NULL)
        {
            return;
        }
    }
    //  初始化数组
    for (i = 0; i < M->m; i++)
    {
        for (j = 0; j < M->n; j++)
        {
            p[i][j] = 0;
        }
    }

    // 将非零元素值放入对应位置
    for (i = 0; i < M->t; i++)
    {
        p[M->data[i].i][M->data[i].j] = M->data[i].v;
    }

    // 打印稀疏矩阵的总函数和列数
    printf("row=%d, col=%d\n", M->m, M->n);
    // 打印值
    for (i = 0; i < M->m; i++)
    {
        for (j = 0; j < M->n; j++)
        {
            printf("%d\t", p[i][j]);
        }
        printf("\n");
    }
}

// 按三元组形式输出稀疏矩阵
void printMatrixByTriplet(SparseMatrix *M)
{

    // 打印稀疏矩阵的总函数和列数
    printf("row=%d, col=%d\n", M->m, M->n);
    // 打印三元组中存放的稀疏矩阵中所有非零元素的所在行、所在列以及值
    for (int i = 0; i < M->t; i++)
    {
        printf("(%d, %d, %d)\n", M->data[i].i, M->data[i].j, M->data[i].v);
    }
}